// 236.二叉树的最近公共祖先
package Leetcode_Second_Brush;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Solution236 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // <原节点，它的祖先>
        Map<TreeNode, TreeNode> ancestors = getAllAncestors(root);

        Set<TreeNode> ancestorsQ = new HashSet<>();

        while (p != root) {
            ancestorsQ.add(p);
            p = ancestors.get(p);
        }
        ancestorsQ.add(root);

        while (!ancestorsQ.contains(q))
            q = ancestors.get(q);

        return q;
    }

    private Map<TreeNode, TreeNode> getAllAncestors(TreeNode root) {
        if (root == null)
            return null;
        Map<TreeNode, TreeNode> result = new HashMap<>();
        if (root.left != null) {
            Map<TreeNode, TreeNode> left = getAllAncestors(root.left);
            if (left != null)
                result.putAll(left);
            result.put(root.left, root);
        }
        if (root.right != null) {
            Map<TreeNode, TreeNode> right = getAllAncestors(root.right);
            if (right != null)
                result.putAll(right);
            result.put(root.right, root);
        }
        return result;
    }


}
